package com.sheng.leetcode.year2023.month11.day27;

import org.junit.Test;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

/**
 * @author by ls
 * @date 2023/11/27
 * <p>
 * 907. 子数组的最小值之和<p>
 * <p>
 * 给定一个整数数组 arr，找到 min(b) 的总和，其中 b 的范围为 arr 的每个（连续）子数组。<p>
 * 由于答案可能很大，因此 返回答案模 10^9 + 7 。<p>
 * <p>
 * 示例 1：<p>
 * 输入：arr = [3,1,2,4]<p>
 * 输出：17<p>
 * 解释：<p>
 * 子数组为 [3]，[1]，[2]，[4]，[3,1]，[1,2]，[2,4]，[3,1,2]，[1,2,4]，[3,1,2,4]。<p>
 * 最小值为 3，1，2，4，1，1，2，1，1，1，和为 17。<p>
 * <p>
 * 示例 2：<p>
 * 输入：arr = [11,81,94,43,3]<p>
 * 输出：444<p>
 * <p>
 * 提示：<p>
 * 1 <= arr.length <= 3 * 10^4<p>
 * 1 <= arr[i] <= 3 * 10^4<p>
 */
public class LeetCode0907 {

    @Test
    public void test01() {
//        int[] arr = {3, 1, 2, 4};
        int[] arr = {11, 81, 94, 43, 3};
        System.out.println(new Solution().sumSubarrayMins(arr));
    }
}

class Solution {

    int MOD = (int) 1e9 + 7;

    public int sumSubarrayMins(int[] arr) {
        // 求出数组 arr 的每个连续子数组中最小的元素之和
        int n = arr.length;
        int[] left = new int[n];
        int[] right = new int[n];
        Arrays.fill(left, -1);
        Arrays.fill(right, n);
        Deque<Integer> stk = new ArrayDeque<>();
        // 计算以 i 为最小值的左边界和右边界
        for (int i = 0; i < n; ++i) {
            while (!stk.isEmpty() && arr[stk.peek()] >= arr[i]) {
                stk.pop();
            }
            if (!stk.isEmpty()) {
                left[i] = stk.peek();
            }
            stk.push(i);
        }
        stk.clear();
        for (int i = n - 1; i >= 0; --i) {
            while (!stk.isEmpty() && arr[stk.peek()] > arr[i]) {
                stk.pop();
            }
            if (!stk.isEmpty()) {
                right[i] = stk.peek();
            }
            stk.push(i);
        }
        long ans = 0;
        for (int i = 0; i < n; i++) {
            // 计算
            ans += (long) (i - left[i]) * (right[i] - i) % MOD * arr[i] % MOD;
            ans %= MOD;
        }
        return (int) ans;
    }
}
